package priv.sort.counting;

public class CountingSort {
    public static void sort(int[] arr) {
        if (arr.length < 2) return;
        int min = arr[0], max = arr[0];
        // 计算 min 和 max
        for (int value : arr) {
            if (value < min) {
                min = value;
            } else if (value > max) {
                max = value;
            }
        }

        // 计算计数数组
        int[] countArray = new int[max - min + 1];
        // 计算索引和出现次数
        for (int i : arr) {
            countArray[i - min]++;
        }
        // 将计数数组输出返回到原数组
        for (int arrIndex = 0, countIndex = 0; countIndex < countArray.length; countIndex++) {
            // 毫无可读性(╯°□°）╯︵ ┻━┻
            while (countArray[countIndex]-- > 0) {
                arr[arrIndex++] = countIndex + min;
            }
        }
    }
}
